BitMachine 是 CSCall C++ 程式庫中的一個 class,可以說是圖靈機(Turing Machine)的一
種改良實作模型。它不是憑空提出的獨立研究概念,而是實際存在於 CSCall 程式庫裡、可>以直接編譯執行的程式碼,同時兼具實務與理論上的用途。
會做出 BitMachine,最初是想解決一些具有 O(2^N) 指數複雜度的老問題(像是電路佈局、>旅行推銷員問題 TSP 等)。不過做到後來發現,光靠這個角度沒辦法真的解掉那個複雜度,得
另外想辦法。有意思的是,整個想法並不是先有數學理論才動手寫程式,而是反過來——從實作
的過程中,一步一步摸索、長出理論來的。
如果只看最初那版實作的程式碼,其實不難;但如果要講清楚「為什麼要這樣設計」「各個元
件之間怎麼互相配合」,以及它跟傳統圖靈機到底差在哪,就會牽涉到不少比較深的理論鋪陳
了。
全文份量不小,我懶得拆成好幾篇連載,所以直接分成兩個部分:
實作概念的形成過程——BitMachine 是什麼、為什麼設計成這樣、想處理哪些問題。
理論基礎——這套設計背後的思考脈絡,以及 BitMachine 架構是怎麼一步步成形的。
後半部的份量比前半部多不少,也偏理論。如果你只對程式設計本身有興趣,看完前半部就能
掌握 BitMachine 的基本概念;如果想知道整套想法是怎麼一路推演出來的,歡迎繼續往下讀
後半部。
本文提出之構造性視角絕非憑空虛設的純粹符號。EMF（Operational Evaluation
Mechanism Framework）理論架構與其核心狀態機（BitMachine）早於程式代碼與機械
邏輯層次獲反覆印證，達到穩定（Stabilized）狀態。
本研究嘗試從操作主義出發，為邱奇-圖靈論題（Church-Turing Thesis, CTT）建構
出嶄新的、基於有限步操作與構造性邏輯的詮釋（Interpretation）。本文對 CTT
之詮釋可簡述為一句話：
形式語言（含數學邏輯符號系統）之表達能力，不超過程序語言與演算法
之表達能力；位元機（BitMachine, BM）即為圖靈機（TM）之具體實作
模型。
本研究內容涵蓋範疇廣泛且具高度內聚性，旨在為理論數學與計算機科學邏輯之間
建立一套物理可驗證、高度內聚的全新轉譯層。
對慣於形式符號推導的純數學讀者而言，本文欲傳達之核心觀念可歸結為一句話：
程式代碼即形式證明（Code is Formal Proof）。一個形式證明，本質上是依既定
規則對符號串所做的一連串確定性變換；一段程式的執行，本質上是依指令集對
記憶體狀態所做的一連串確定性變換。兩者在操作層次上並無本質差異——差別
僅在於前者慣以紙筆書寫、後者可交由機器實際執行並驗證終止與否。這也是本
系統將「數字」與「一般文字」同視為同一離散符號範疇之子集的緣故（見公理
二）：數學物件既可用文字定義、亦可用可執行的程序定義，二者在構造層次上
彼此互通。準此，數學問題原則上皆可、也應該以程式的方式加以表述、處理與
檢驗，而非僅停留於符號層面的抽象宣稱。
本研究主張，ZFC 集合論所依賴的實無限與非構造性存在宣告——其典型代表即為無窮
公理（Axiom of Infinity），該公理並非以任何可操作程序構造出無限集合，而是
直接宣告其作為已完成整體之存在——無法滿足本文公理三（物理對應性）所要求的
科學構成要件：其語意無法還原為可觀察、可重複操作之物理程序。本文進一步指出，
課本數學中依賴此類非構造性存在宣告所推導之結果（如極限、連續體、代數封閉性
命題等），其論證基礎同樣不滿足公理三，因而不具備被客觀驗證、視為既定科學
事實之正當性——這使得這類命題目前應被視為懸而未決之開放問題，而非已證定論。
本文據此提出一套具備明確硬體邊界的新型構造性公理系統——EMF 系統（EMF 泛指所有
本文、REG 資料與總結，原字由 External Memory File 演化而來）。
本文核心聚焦於「邱奇-圖靈論題」的構造性詮釋，主張數學與邏輯等形式語言的表達
能力，實質上不超過程序語言與演算法的表達能力。系統底層基於「位元機」
（BitMachine，即傳統圖靈機的 C++ 實體化模型），將無限大重構為「永不休止之
指令迴圈」，並確立基於機械式減法運算的嚴格等價判定。透過將考拉茲猜想與
P vs NP 問題轉換為可終止性演算法與物理記憶體限制的衝突，本系統得以將傳統
推導中殘留的主觀幻覺徹底掃除使得問題容易解決。本文並主張「程式代碼即形式
證明」（Code is Formal Proof）：凡可於位元機上終止並驗證之程序，即構成
一等價於傳統形式證明之操作性證明，數學問題因而可以程式方式處理。
關鍵詞：邱奇-圖靈論題（Church-Turing Thesis）、位元機（BitMachine）、
操作優先本體論（Operationalism）、構造性數學、連續體批判、通用圖靈機批判、
動態無限集（MSet）、形式證明與程式碼等價性（Code is Formal Proof）。
傳統古典數學的形式公理系統與 ZFC 集合論，在建立高度抽象的數學概念
時，常因符號的過度推演而脫離客觀實體。其根本盲區在於：古典邏輯試圖
以靜態、一步到位的方式去宣告一個「已經完成的整體」（如實無窮）。
然而，回歸物理現實與認知科學，任何實質意義上的「計算」與「構造」，
本質上都是一個從「部分」逐步推導、漸進發展至「整體」的動態歷程。
因為程序與圖靈機（TM）內嵌了執行順序（時間）與內部狀態空間（空間
排他性），能夠完美承載並描述這種由局部操作累積成宏觀整體的事實。
在事實表達能力與客觀嚴謹度上，程序語言與演算法必然超越缺乏動態
階層概念的傳統邏輯或 ZFC 集合論。
為了使數學基礎論重回可觀察、可操作的客觀範疇，我們有必要從計算科學的根本
視角出發，將數學物件還原為具備內部資訊結構、由部分至整體遞迴生成的程序與
離散符號。
本系統所提及之「命題」與「證明」，其語意嚴格建立於下方「操作優先」
之公理之上。
本系統框架下的『證明』，與傳統 ZFC 集合論中缺乏實體的純粹符號遊戲截然不同，
亦不承認非構造性的抽象極限。本系統之證明，本質上是在具備有限物理定址與空間
排他性之位元機（BitMachine）上，程序執行的終止性、複雜度下界與編碼限制之
必然性檢驗。凡無法在實體程序或有限步驟中操作、驗證之客體，不具備本系統之
存在性與等價性。
本系統之推導，嚴格建立於以下三條不可跨越之底層離散公理基礎之上；其中，公理一
首先界定本文一切推導所及之「對象」的存有範疇——換言之，凡本文其後所討論、
操作、證明之客體，無論是數學符號、命題敘述、程序碼、抑或自然語言本身，皆已
預先被公理一收攝為同一離散符號範疇下之「文字」，此為本文得以將數學問題、
邏輯命題與程式碼等量齊觀、交互處理之最初立足點：
＊公理一（離散性，Discreteness）：
一切以文字表示的數學實體皆為有限長度的離散符號空間。傳統數學所謂的「無限大」
或「無限小」，在本系統中並非實體數值，而是一道「永不休止之指令迴圈（Non-
terminating loop）」之程序標籤。凡本文以下所處理者——無論命題、證明、程式碼
或磁帶上之狀態——皆不出此離散符號範疇之外；此範疇界定，即為本文一切後續構造
之起點。
＊公理二（操作優先，Operation-First Identity）：
一個數學物件唯有在其操作行為被明確定義後，該物件才獲得存在性，即：存在性
等價於可操作性（Existence = Operationalizability）。數字可視為文字的子集，
文字亦可視為數字的子集——兩者皆是有限長度的離散符號串，差別僅在於其上定義
了何種操作（數字習慣定義加減乘除，文字習慣定義連接、比對等），並無範疇上
的高低之分。故對純數學讀者而言，「數」不必被賦予任何超越符號本身的先驗
本體地位；一旦其操作被程序明確定義，該數學物件即與一段合格的程式碼等價，
可交由機器實際執行、驗證。一般形式公理系統中的術語與符號常被過當使用，
難以從所謂的「抽象數學概念」中客觀地推斷出任何東西，往往淪為主觀想像。
同時，現行的形式系統無法描述程序性事實，而程序性邏輯早已用於設計數位
電腦並驗證無誤。必要時採用虛擬 C++ 程序語言來精確描述數學物件。
公理二所要求的，正是語意物件必須與其操作同時給出定義，方能宣告該物件存在
——此點類同於物件導向（Object-Oriented）程式設計中，一個類別（class）的
定義必須同時包含其資料結構與其上可執行之操作（成員函式），二者缺一不可。
將此原則貫徹至底層實作，即產生了本文之核心構造：位元機（BitMachine）。
位元機作為一個同時承載「離散符號資料」與「其上可執行操作」之統一實體，使
得原本散落於數學、邏輯、程式碼等不同表述系統中的文字知識，得以在同一套
可操作、可驗證的框架下被統一表達。也正因為這種統一表達，許多長期懸而未決
的難題，得以交由電腦程序協助釐清、化簡甚至直接解決——其中不在少數，追本
溯源，其實源自人類自身在缺乏操作定義的情況下所自創之矛盾概念（如羅素悖論、
理髮師悖論等），一旦還原至公理二所要求的操作性定義，這類悖論往往即可被具體
定位、拆解。
由於目前所使用的等號的語意模糊,目前提議等號的定義(因'-','0'已有定義):
a = b iff a - b = 0
此定義僅於等價判定含糊或未定義時"參考使用"（由公理二，數 0 與其加減運算
須同時定義方能使用此判定）。若兩個物件之等價判定發生模糊，必須回歸至位元
機（BitMachine）的磁帶上執行減法運算。當且僅當差值返回 0（或空字串 Null）
時，等價宣告方成立。
＊公理三（物理對應性，Physical Correspondence）：
理論之語意最終必須對應物理現實，否則無法客觀驗證、傳遞與應用——凡無法對應
物理現實之理論宣稱，即使於其自身符號系統內部自洽，亦不具備應用於現實計算
與工程之正當性。此一規範並不僅適用於本系統，亦同等適用於「課本數學」及一切
自命為科學之理論：任何理論若欲被稱為「科學」，其語意即須可還原至可觀察、可
重複操作之物理程序，此為科學一詞之構成要件，而非本系統額外附加之限制。此即
REG_04〈什麼是証明〉一節中，以點間距離公設推導畢氏定理之例證所欲揭示者：
透過物理實驗（或可操作之程序）尋找、驗證數學真理是有效的；反之，若一個數學
想法無法讓其在現實中被客觀重現，該想法即有問題。此一判準——姑且稱之為「數學
＝物理」——貫穿本系統與 REG 系列全部推導，並是本文據以評斷古典理論中各項非
構造性宣告之最終依歸。
由此亦可引申一項隱含推論：所謂「可被科學解釋的宇宙」，其範圍並非自然給定、
獨立於人之外的既成事實，而是隨人類所建立、且滿足公理三對應性要求之理論體系
範圍而劃定——是人為構造、逐步擴張的產物，而非先驗存在的固定疆界。與此相應，
凡滿足公理三之理論，其全部語意內容原則上皆可還原為有限長度之離散文字知識，
因而皆可於位元機（BitMachine）之磁帶上具體表現、儲存與操作；反之，任何無法
在磁帶上以有限步驟表現之宣稱，即已逾越公理三所劃定之科學界線。
底層架構上，本系統引入位元機（BitMachine）與軟處理單元（Soft-Processing
Unit, SPU）架構。此處必須明確界定計算的本質（如 Computation-zh 研究所述）：
計算絕非脫離實體的抽象概念，而是一個基於確定性操作與狀態轉移的動態系統。
真正的計算，其基礎必須完全建立在具備物理定址排他性、空間與時間邊界的硬體上。
位元機作為圖靈機的實體化，其關鍵創新在於「不將磁帶（Tape）視為機器自身的
固有組成部分」，此設計解決了傳統圖靈機理論中關於無限大的邏輯悖論。同時，
這種基於實體定址限制的系統構造，徹底否定了缺乏物理支持的超計算
（Hypercomputation ）或理想化數學模型。其實作證明了程序語言只要具備條件分支
與全磁帶定址能力（暗示 「問題複雜度 == 所須最少判斷數量」，並與使用的運算
函數不直接相關），基本上即達圖靈完備性（Turing Completeness），這也為整個
離散數學的底層重建奠定了物理可驗證((Physical Realizability))的磐石。
傳統形式證明是在一形式系統中，依公理與推理規則，對符號串進行有限步的
合法變換，直到抵達目標命題為止；此一過程本身即是一個確定性的、依規則
逐步執行的程序。程式碼的執行，同樣是在既定的指令集與記憶體模型下，依
指令逐步對狀態進行合法變換，直到程式終止（或證明其不終止）為止。二者
的操作結構完全同構：
形式系統之公理與推理規則 <--> 程式語言之語法與運算子語意
形式證明之推導步驟 <--> 程式執行之指令步驟
證明抵達目標命題 <--> 程式終止並回傳預期結果
證明不存在／命題不可證 <--> 程式不終止或無合法輸出
因此，「證明某數學命題成立」與「撰寫一段程式並驗證其終止且輸出符合
命題所述」，在本系統中是同一件事的兩種表達方式；差別僅在於後者可交由
位元機實際執行，其終止性、複雜度下界與編碼限制皆可被客觀觀測、重複
驗證，而非僅停留於紙上符號的主觀認定。這正是本文選擇以虛擬 C/C++
程式描述數學命題（如本文命題 1～9 及後續各節）的根本理由：程式代碼
在此並非「輔助說明」，而本身就是形式證明。
古典數學基礎論習慣將自然數系統奠基於皮亞諾（Peano）公理系統。
該系統透過後繼函數（Successor Function）S(n) 靜態地定義自然數的
生成。然而，從程序運作與演算法的視角審視，皮亞諾公理存在一個本
質性的內在局限：它僅給出了生成後繼的遞迴規則，卻從未對該生成程
序的「終止性（Termination）」給予明確的邏輯說明。
這種缺乏終止性宣告的形式化，導致了系統在嚴格的邏輯推理下，產生
了巨大的語意盲點。在古典形式系統中，我們既無法容納「無限大（∞
）屬於自然數集合 N」的陳述，亦無法在系統內完備地證明「∞不屬於
N」。這種邏輯歸屬的模糊性，使得後續的數系定義、極限理論與稠密
性等定律，全然依賴於一個盲目延展、缺乏邊界控制的公理基石，其系
統性的盲點與失誤便不可避免。
為了修正此一脫離客觀實體過度的抽象，我們必須引入邱奇-圖靈猜想
（Church-Turing Thesis, CTT）。本文對 CTT 之詮釋，並非憑空立論，
而是直接建立在 REG_02〈何謂「計算」〉一節所給出之操作性定義之上：
該節將「計算」界定為「由基本〔部份〕的決定性運算到整體表現的一個
動態系統的運算過程」，其輸入、輸出與中介狀態皆由固定有限之〔部份〕
(可具體對應於離散文字符號)所構成。正是由於「計算」在此已被還原為
一組可具體操作、逐步執行之離散步驟，我們才得以據此推得本文開篇所
述之 CTT 詮釋——形式語言之表達能力不超過程序語言與演算法之表達
能力；換言之，CTT 詮釋是 REG_02 計算定義應用於形式語言範疇後的
直接推論，而非另立之獨立宣稱。CTT 表明，任何直觀上可計算的函
數或程序描述（演算法），比一般建立形式系統的傳統古典邏輯具備更
強、更客觀的事實表達能力。在 CTT 的程序性視角下，「無限（
Infinity）」本質上並非一個已然實存的靜態實體，而是一個「永不終
止的程序迴圈（Infinite Loop）」。其底層的動態語意，可由現代計
算機科學的虛擬碼給予毫無歧義的精確表述：
wij2
for(;;) {
P(); // 重複執行某特定性質或代數運算 P
}
// unreachable code (不可達邊界)
藉由在迴圈中引入不同的命題或算式 P，我們能清晰、具體地描述無限
級數、無限自參、乃至不可判定性（如停機問題）。這種將數學物件還
原為「可操作實物」的構造方式，其嚴謹度與事實表達力顯著優於將簡
單概念極度抽象化的傳統形式理論。
延續前文一節所確立之公理一（離散性）、公理二（操作優先）與公理三
（物理對應性），我們將其具體套用於自然數系統之構造，得出以下三項
對應本節脈絡之具體化陳述——此三者並非另立新公理，而是前述三條底層
公理在自然數構造情境下的具體展現：
公理 1：自然數為有限計數步驟、有限長度的離散符號（字串）。
公理 2：物件（如數、圖形）與其操作性質，同時由定義而存在。
公理 3：自然數之構造與運算，最終須能對應、還原至可具體操作之物理
實現——例如以石堆、算籌（算盤珠、成束棍子等）之增減操作具體示
現。凡無法以此類實體操作重現、驗證者，不具備本系統所認可之自然
數存在性。
以公理 3 為例：「後繼」（successor）此一操作，若還原至最原始的實
體操作層次，即對應於在既有的一堆石子（或一束算籌）旁再放上一顆石
子（或一根籌）；「加法」對應於將兩堆石子併為一堆後重新計數；「兩
數相等」則對應於兩堆石子經一一對應（逐一配對移除）後恰好同時取
盡、無所剩餘。這種可由任何觀察者具體操作、肉眼驗證之堆石／算籌程
序，正是自然數理論最終得以被物理現實支持、而不僅停留於符號宣稱的
根本理由：凡數學理論中對自然數所作的陳述，最終都應能以此類具體、
有限、可重複操作的實體堆疊程序加以印證。
在此框架下，「符號長度有限」是構造的根本基石。我們不再將自然數
集視為一個包含無窮多元素的靜態實體集合，而是將其建構為一組「假
設容量無上限的動態陣列與判別程序」。其生成與判別邏輯可透過以下
程序結構明確表達：
typedef String NaturalNumber;
NaturalNumber N[] = {0}; // 初始化自然數陣列
NaturalNumber next_natural_num(NaturalNumber n) {
return mak_next(N, n); // 由當前狀態製造下一個自然數符號
}
bool is_natural_num(NaturalNumber n) {
if (is_format_correct(n) == false) return false;
if (contain(N, n)) return true;
NaturalNumber m = get_max(N);
for(;;) {
m = mak_next(N, m);
insert(N, m); // 將新生成的動態符號存入陣列
if (n == m) return true;
}
return false; // 不可達
}
上述程序表明了兩點深刻的數學實質：
第一，「數」本質上並非不可言說的抽象本體，而是符合特定格式、能
接受後繼函數等操作的離散符號表達式（字串）。
第二，古典數學中所說的「所有自然數」，其程序語意是指「可任意指
定的特定自然數」，而「所有自然數的集合 N」在現實中並不意味著一
個已然實存的靜態無限集，而是一個處於動態建構中、永不終止的程序
邊界。
當自然語言的抽象論證涉及多個無限集合時，若缺乏此類程序界定，極
易犯下概念混淆的錯誤。例如古典理論中將偶數集定義為 {0, 2, 4,
6, ...}，在進行對比推論時，偶數集中的 2 與 6 容易與原自然數定
義產生符號混淆；若改採程序化符號（如 N<1, S> 或 N<0, +2>），則
可透過底層程序的獨立狀態空間，有效杜絕概念歧義。
當我們確立了自然數的程序構造後，許多被古典邏輯視為普適的「代數
封閉性」命題，其適用邊界必須依據公理及無限的義意予以重新修正。
命題 1：N + N = N（即若 a, b ∈ N => a + b ∈ N）僅在有限加法
步驟下成立。
論證：非零自然數的累加會使符號長度嚴格增加。一旦允許無限步驟的
累加，將得到「無限長的符號」，由公理 1 可知，此類無限長符號已
然越過構造邊界，不再屬於自然數。
命題 2：Q + Q = Q（有理數對加法的封閉性）僅在有限加法步驟下成立。
論證：正有理數 q 在累加時其分子或分母的數值與符號長度會嚴格增
加。在無限項加總 q = a/b = q₁ + q₂ + q₃ + ... 時，其分子 a
或分母 b 必然包含無限長的符號（不論該級數在古典意義下是發散或
收斂，其程序底層皆包含了無限長的符號表達）。這意味著，無限項加
總的結果已然越過有理數的代數邊界。
這一邊界限制直接打破了古典數學對「循環小數」的固有認知。在形式
邏輯無法妥善處理無限程序的情況下，古典理論誤認為循環小數是有理
數，但從程序構造來看：
命題 3：循環小數本質上為無理數。
論證：設循環小數 x (0 < x < 1) 具有循環節 S，寫作
x = 0.S₁S₂S₃...S_∞。依定義展開為：
x = S₁/b + S₂/b² + S₃/b³ + ... + S_∞/b^∞ (b ∈ N)
此式本質上是 Q + Q 在無限項加法下的特例。由命題 2 可知，無限
項加總的結果不再是有理數，即為無理數。因此，嚴格的算術恆等式應
修正為：
1/3 = 0.333... + 非零餘數
古典所謂「有理數皆可寫成循環小數」的命題，在考慮了 CTT 程序終
止性與符號長度極限後，是不成立的。這進一步說明了，傳統形式系統
在面對無限程序時，往往因缺乏動態限界而陷入邏輯盲區。
古典代數極常依賴特定形式技巧來強行宣告 0.999... 與 1 完全等值
（例如令 x=0.999..., 則 10x=9.999... = 9+x ⟹ 9x=9 ⟹ x=1）。然而
回歸 EMF 構造系統，根本沒有任何一條公理允許我們在無限程序中直
接宣告 10x = 9+x 與原式等價。此處理方式忽略了無限程序的動態結
構。若 0.999...=1 恆成立，則正整數的質數唯一分解定理將在邊界失
效。因為極限 lim(n→無限) (1 - 1/n) 與實體數值 1 是全然不同的兩
碼事。極限的精髓在於提供一種不藉由等式來描述數（特別是無理數）
的方法，而非「最後那一項等於 1」。
綜上，關於實數與無限大的完整推導、逐項命題檢驗與更細緻的爭議處理，收
錄於 REG_04〈實數與無限大〉。就本系統之定位而言，可歸結為以下判準：
課本數學中，依賴實無限與非構造性存在宣告（完備性公理、選擇公理
等）所推導、並將 Q+Q=Q、稠密性等代數封閉性命題不加區分地套用於
無限大情境的部份，在公理一、二、三的觀點下是內部矛盾的——因為
這類命題本身僅在有限步驟下為恆真式，此為公理一、二、三成立之後
的必然結論，無須另外構造冗長的形式證明。
需要澄清的是，本文的目的並非攻擊或推翻課本理論本身，而是指出：多數
人之所以覺得這類命題在無限大情境下依然理所當然成立，是因為長期依賴
課本「直觀延伸」的講法，而未曾在無限步驟下逐一檢驗其是否仍為恆真式。
凡課本推導確實仰賴前述非構造性宣告、並將有限步驟下的恆真式不加區分
地套用於無限級數或無限集合者，依公理一、二、三即出現內部矛盾；未涉
及此類宣告的古典結果（如命題 4、9 一類的有限步驟論證），則不在此限。
本節引入考拉茲猜想（Collatz Conjecture，又稱 3x+1 問題）作為檢驗邱奇-圖靈
論題認知邊界的基準工具。傳統數論在皮亞諾公理系統下極難證明此題，本文使用
圖靈機模型（可執行演算法）來判定其終止性。
傳統考拉茲迭代可以寫成以下函數與程序：
int cop(int n) {
if(n<=1) {
if(n<1) { throw Error;
}
return 1; // 1 為迭代終點
}
if(n%2) {
return 3 * n + 1; // 奇數規則
} else {
return n / 2; // 偶數規則
}
}
void rcop(int n) { // 考拉茲迭代主程序
for(; n!= 1;) {
n= cop(n);
}
}
命題 3：對於所有自然數 n≥1，cop(n) 的迭代運算必然終止。
證明：
我們設計一個等價分解程序 rcop2，將變數 n 分解為 n=a+b 的動態形式進行觀測
。
void rcop2(int n) {
int a=n, b=0;
for(; a+b != 1;) { // 測量點 A (a+b 等同於迭代過程中的 n)
if((a%2)!=0) {
--a;
++b; // 動態調整使 a 保持為偶數以利後續算法對等執行
}
// 模擬考拉茲迭代
// 測量點 B
if((b%2)!=0) { // a 為偶數時，等同於判定 (a+b)%2
a= 3*a;
b= 3*b +1;
}
a= a/2;
b= b/2;
}
}
已知代數恆等式：3*(a+b)+1 = (3a)+(3b+1)，且每次迭代皆執行一次除以 2。
假設在測量點 B，每次奇數操作都與一個偶數操作配對，並忽略 --a 與 ++b 的微
小調整，我們可以得到動態軌跡：
a₁= n-1
aₓ= (3aₓ₋₁)/2 =... = (n-1)(3/2)ˣ⁻¹
b₁= 1
bₓ= (3bₓ₋₁+1)/2=... = 2(3/2)ˣ⁻¹ -1
此時觀測兩者的比例關係：
aₓ/bₓ= (aₓ₋₁)/(bₓ₋₁) = ((n-1)(3/2)ˣ⁻¹)/(2(3/2)ˣ⁻¹ -1)
=... = (n-1)/(2- 1/(3/2)ˣ⁻¹)
當 x→∞ 時，該估算值之比例極限趨近於 (n−1)/2. 由於 aₓ 與 bₓ 實質上是
非連續的動態函數，且過程中穿插的除以 2 以及調整運算會迫使 aₓ 更小、bₓ 更大.
因此可以推斷實際的 aₓ/bₓ 值將遞減至終值 0，即最終 a=0.
整个 cop 迭代序列 n₁,n₂,n₃,...,nₓ 可視為一個串級放大過程：
(n₂/n₁)(n₃/n₂)(n₄/n₃)...(nₓ/nₓ₋₁)= nₓ/n₁
當數值極大時，奇數運算的放大率趨近於 3，偶數運算的放大率為 1/2.
系統輸出與輸入的總放大率滿足 nₒᵤₜ/nᵢₙ ≒ 3ˣ/2ʸ ≒ 1.585*(x/y)，其中 x
為奇數運算次數，y 為偶數運算次數.
分析表明，當 n>2 時，相較於 a 從 n 算至 0 的過程，nₓ 從 n 算至
n−1 的動態過程中存在過量的偶數運算（因細節冗長不全列出）。由於 nₓ<n
的狀態必然出現，根據數學歸納法, 即可證明 cop(n) 迭代運算必在有限步驟內
終止。
本節透過 EMF 系統的動態演算法語意，檢驗計算複雜度階層中著名的 P vs NP 問題。
我們定義演算法問題的計算步驟為問題敘述長度（Size, 記為 |q|）的函數。連續
的多項式時間程序（多項式程序）在複雜度分析時，可在演算法步驟中任意增刪或
合併，而不影響其多項式階數。
我們定義一個嶄新定義之非決定性多項式時間範疇——ANP：
ANP = { q | q 為可在 O(2^|q|) 步驟內經由 fnp 演算法模板解決的判斷性問題 }
其中 q 包含一個驗證資料集合 C（滿足 card(C) ≤ O(2^|q|)）以及多項式時間驗
證函數 v: C → {true, false}。其演算法實作模板如下：
// 多項式時間驗證架構模板
Certificate begin_certificate(Problem q);
// 取得第一個驗證元素，若無則返回偽資料 EndC
Certificate end_certificate(Problem q); // 取得結束標記 EndC
Certificate next_certificate(Problem q, Certificate c);
// 取得下一個驗證元素
bool v(Certificate c); // 多項式時間驗證函數
bool fnp(Problem q) {
Certificate c, begin, end;
begin= begin_certificate(q);
end= end_certificate(q);
for(c= begin; c!=end; c= next_certificate(q, c)) { // 最多 O(2^|q|) 迴圈
if(v(c)==true) return true;
}
return false;
}
由於連續 O(P) 數量的 Ptime 函數（或指令）可合併算成單一個 Ptime 函數，在
進行此複雜度分析時，可在算法步驟中任增刪/合併/分割任 Ptime 函數而不影響
算法的複雜度。或許最後只需考慮判斷分枝的數量。ANP 問題 q 可以 q<v, C> 表達。
命題 4：ANP 集合與傳統 NP 集合等價（ANP = NP）
證明：由於所有傳統非決定性圖靈機（NDTM）定義下的 NP 完全問題（NPC）皆可全
歸約至 fnp 模板的程序中，且其驗證資料數量為 O(2^|q|) 等級，
故 NPC ⊂ ANP ⟹ ANP = NP。
命題 5：NP 完全問題（NPC）的最低複雜度下界為 O(2^N)
證明：計算在本質上屬於漸進發展的動態歷程，計算機經過 n 步驟後的狀態總可分
為「局部成果」與「剩餘問題」兩部分。我們可在原有的分治演算法（banp）中加
入一個名為「輔助資訊」的 AuxInfo 物件，用以存放計算完局部子問題後的成果，
將其改寫為 banp2：
bool banp2(Problem q, AuxInfo* ibuf) {
if (certificate_size(q) < Thresh) { // Thresh 為一微小常數閾值
return solve_thresh_case(q, ibuf); // 常數時間內解算
}
Problem q1, q2;
split_certificate(q, q1, q2); // 任一多項式時間算法將 q 二分割為 q1, q2
AuxInfo I;
if (banp2(q1, &I) == true) { // 遞迴計算子問題 q1，並將有價值資訊存入 I
write_ibuf1(ibuf, q);
return true;
}
bool rv = banp2_i(q2, &I);
// 在給予輔助資訊 I 的情況下解算 q2
write_ibuf2(ibuf, q);
return rv;
}
若要使 banp2 演算法將 NPC 問題的複雜度降低至更低級別，則 AuxInfo I 必須產
生對「其餘所有局部子問題」都能提供足夠加速的通用整體特徵。然而，在物理
限制下，這類包含全系統映射的輔助資訊 I，其輸入/輸出編碼將耗費無限的時間與
儲存空間。在從部分走向整體的動態歷程中，這種瞬時且全知的信息跨越，在基於
物理磁帶定址的位元機系統中是不可能的。
結論：由命題 5 可知，NPC 問題的物理複雜度不小於 O(2^N)，故 P ≠ NP 成立。
第三、四兩節分別針對考拉茲猜想（另見 REG_01）與 P vs NP 問題（另見 REG_03）
給出之演算構造性論證，其意義並不僅止於個別命題本身之成立與否，更在於具體
展示：在 CTT 詮釋下，將問題轉換為可執行、可終止性檢驗之程序後，原本在傳統
公理化推導下極為冗長、甚至懸而未決之難題，其複雜度往往可被大幅簡化——考拉
茲猜想藉由 rcop2 之等價分解程序、P vs NP 問題藉由 ANP 範疇與物理定址限制之
引入，皆是實例。這正呼應了本文所主張之「程式代碼即形式證明」（Code is
Formal Proof）：命題 3 與命題 5 之證明，其推導步驟並非傳統意義下單一方向、
逐行展開之邏輯線性推導，而是以程序之等價變換、狀態觀測與終止性檢驗為骨幹
——這說明形式證明本不必被限定為傳統邏輯式的線性推導鏈。此一體悟，亦與本文
第二節所揭示之問題根源相互印證：古典邏輯中被視為恆真式（tautology）的代數
封閉性命題，一旦套用於涉及無限之情境，其結果未必仍為恆真——既然「恆真」本
身在無限範疇下已不可盡信，緊守單一線性推導鏈的傳統證明形式，其可靠性自然
也隨之受限，而程序性、可終止性驗證的證明方式，則提供了一條可具體操作、
不受此限制之替代路徑。
本節基於近年所累積之 CTT 詮釋經驗，從「資訊複雜度」、「程序形式化」與
「動態無限集」出發，重新審視傳統計算理論之核心基石。
命題 6：在「系統容量與狀態符號集受限」的實體物理模型中，不存在一個絕對萬能
的通用圖靈機（Universal Turing Machine）。
論述：儘管對於任意給定的圖靈機 M，我們總能建造一個功能上等價的模擬器（模擬
機器）M'；但任何實際具備模擬能力的圖靈機 M_sim，其元狀態（Meta-states）與
元符號（Meta-symbols）的資訊複雜度（熵）必然嚴格大於被模擬的對象。
另一種說法是，模擬器的規模（Size）會比其模擬對象大。此外，通用模擬器無法
在其自身的複雜度限制下，模擬複雜度大於或等於自身的機器（包括它自己）。這與
停機問題（Halting Problem）的對角線論證在精神上互補。
簡證（基於位元機 BM 模型的結構約束）：
建立位元機（BM）模型時，首先就會發現，任何模擬器為了執行解碼、定址與規則
比對，必然需要使用比被模擬對象（磁帶上的目標 BM）更多的符號及節點（
num_nodes，相應於圖靈機的狀態 state）。因此，模擬器在實體結構上無法完全
映射並模擬自身，故得證。
計算問題的程序語言化定義的核心觀點: 任何實質意義上的「計算問題」，其初始
與正式的問題敘述，必須能夠被形式化為某種程序語言（或等價的形式語法模型）。
正如一個未經數學公式建模的物理直覺不能被稱為「數學問題」一樣，一個無法以
有限程序結構、有限輸入/輸出映射表達的宏觀描述，根本不具備可計算性。程序語言
不只是「解題的工具」，程序語言本身就是「定義問題邊界（Problem Statement）
」的唯一媒介。否則該問題不是計算機問題。
經典邏輯之靜態盲區與動態演算法解方（消除悖論）：
傳統一階邏輯與經典集合論試圖將「無限」定義為一個靜態完成的實體（Actual
Infinity），這種缺乏時間與步驟概念的表達方式，是引發諸多對角線悖論（如羅素
悖論、理髮師悖論）的根源。基於傳統邏輯，含無限概念的知識或問題表達常含悖論，
而位元機（BM）的觀念與表達方式可有效消除這些問題。
一般來說，解題通常需要先建立一個無限集 MSet 表明所處理的案例（case）。在
「CTT 詮釋」 或BM 表達模型中，我們引進了程序概念（Dynamic/Procedural
Notion）。此處的無限集 MSet 不是一個擺在那裡、已經完成的靜態對象，而是一個
由特定規則、可遞迴產生的「動態生成程序（Dynamically Generating Process）」。
因為程序具備「運作狀態（State）」與「執行順序」，它在任意特定時間點都只表現
出有限的具體狀態，從而在根本上消除了傳統靜態無限邏輯中，因「將過程（部分）
誤認為狀態（整體）」而產生的邏輯悖論。
本文所呈現的架構，並非預先設計完成的體系，而是在持續檢驗各項命題一致性的
過程中，逐步浮現的整體結構。本文至此前後所建立的公理、BitMachine、CTT 詮釋，
以及「Code is Formal Proof」等觀點，看似分屬數學、計算理論與程式設計等不同
領域；然而，它們共同揭示了一件事情：所有可客觀操作、可驗證、可推理的文字
知識，皆可還原為離散文字及其操作。
由 BitMachine，便自然導出一種能夠統一描述各類知識的共同表示語言 BML（參見
REG_07）。BML 並非特定的程式語言，而是一種共同的底層表示方式（BM graph）：
一段知識，無論其來源是「案例」（case，如觀測資料、標註樣本，其建構方式在意義
上等同於 AI 的 data-label 過程）或「規則」（rule，即傳統撰寫程式的方式），
最終都對應到同一個 BM graph 上的節點與轉移規則。舉一個較貼近直覺的例子：
一套天氣預測系統，一部分知識來自大量歷史觀測資料（case，帶著標籤的「今天長
這樣、明天就那樣」），另一部分則來自物理定律所寫成的方程與程式（rule）。
傳統上，這兩種知識分別棲身於「訓練資料／模型權重」與「原始碼」兩套互不相通的
載體；BML 的主張是，兩者其實可以還原為同一個 BM graph 上不同來源的節點，因而
能在同一個框架下混合建構、混合優化，而不必被迫二選一。
這件事值得追求，不只是理論上的簡潔。現行以類神經網路為代表的 AI 系統，其知識
隱藏於連續的權重矩陣中，難以驗證、難以解釋；傳統程式碼則相反，可驗證、可推理
，卻難以直接從資料自動生成。BML 若能成立，理論上便提供了兩者之間的橋樑：
類神經網路訓練所得的隱性知識，原則上也可透過「反組譯／多重語意投影」（見
REG_07 理念 5）還原為離散、可讀、可驗證的 BitMachine 操作序列。這與「可解釋
AI」（Explainable AI）與形式驗證（Formal Verification）近年來的訴求方向一致
，也呼應本文開篇所主張的「Code is Formal Proof」：若一段知識最終能還原為可
終止、可驗證的程序，其可信度便不再仰賴對黑盒模型的信任，而可回歸至公理二
（操作優先）所要求的、可具體檢驗的操作性定義。
然而，必須指出，BML 目前仍停留在初期開發層次，距離真正可用的統一表示語言，
尚有數項未解的具體問題：其一，add_case 與 add_rule 交叉混合建構下，BM graph
的最佳化是否收斂、其複雜度為何，目前僅是「理想上」的期望，尚無具體演算法或
複雜度上界；其二，「反組譯成更高階語言」時、資訊在投影過程中是否會遺失，尚待
形式化證明；其三，目前僅有 REG_07 所定義的語法（BNF）與手工組譯範例，缺乏
實際可執行的編譯器／解譯器原型，更遑論具規模的 benchmark 驗證。
這些限制不代表 BML 這個方向不成立，而恰恰說明了它目前的定位：一個由本文理論
自然推導出、但尚待數學、計算機科學、人工智慧、程式語言及知識工程等多方共同
參與才能落實的下一階段研究方向，而非單一作者或單一研究可一次完成之成果。
一套統一知識表示語言，即使不完整，仍具有相當高的實用性——正如自然語言本身從
未「完整」過，卻不妨礙其作為知識載體逐步演化。BML 即是在此理解下所提出的一個
研究方向，希望作為未來相關研究的共同基礎。
目前的線性公理系統所能處理的敍述/証明能力不如程序語言(算法),以致常產生難解的奇論
問題或悖論(自身矛盾的証據)。以上的導文最初是由AI Gemini 依據人類最佳行文方式歸納
生成(字詞用法可能與原意有些小差異), 並經多輪與Claude,ChatGPT 等不同AI 反覆檢驗、
修訂而成,作者原則上不予更動,當其為另一種視角的描述,因其已呈現本作之整體觀點.
讀者若對本文所述之詮釋視角、底層運行細節或動態行為觀測有進一步興趣，可將本文（或
REG 系列原始文獻）直接輸入給 AI（如 Claude、ChatGPT、Gemini 等），並下令：
「請依本文公理1、2、3與操作主義框架,逐項檢查命題X之推導,指出其中任何邏輯缺口
或與文件自身規則(如公理1、無限級數運算原則等)相牴觸之處,不必顧及課本數學說法,
因課本說法亦須遵守公理1、2、3。
但注意,AI (如同人類)相當能掰,善於避談/誤導/製造幻覺及健忘,不同AI 的檢驗尺度與
用詞習慣也略有差異,讀者宜自行交叉比對多個AI 之回應,而非單憑一次詢問結果定論。
3x+1問題: 對於任意大於或等於1的整數n. 若n為奇數,則乘3加1. 若為偶數則除2.
問題是, 是否所有數經過這種計算一定會算至1? 以下証明此問題答案是肯定的, 一定會
算至1. 皮亞諾公理系統難証此題(或會很長),所以使用算法(圖靈機模型)証明.
考拉茲(Collatz)函數::=
int cop(int n) {
if(n<=1) {
if(n<1) {
throw Error;
}
return 1; // 1為疊代終點
}
if(n%2) {
return 3*n+1; // 奇數規則
} else {
return n/2; // 偶數規則
}
}
考拉茲數::= 若n, n∈N<1,+1>, cop疊代運算最後會算至1(即,cop(...cop(n))=1), 則n為
考拉茲數,否則n不是考拉茲數.
考拉茲問題::= 是否對於所有整數n,n∈N<1,+1>, n為考拉茲數? 換句話說,問題等效於問
rcop程序會不會終止.
void rcop(int n) { // cop疊代
for(;n!=1;) {
n=cop(n);
}
}
命題: ∀n, n∈N<1,+1>, cop(n)疊代運算必終止.
証: 程序rcop2 將rcop中的n等價分解成n=a+b形式表示.
void rcop2(int n) {
int a=n,b=0;
for(; a+b!=1;) { // a+b測量點A (a+b 等同cop疊代過程的n)
if((a%2)!=0) {
--a; ++b; // a,b調整,使得a保持為偶數,以使以下算法能進行並保持對等
// 於cop(n)疊代.
}
// a/b測量點B
if((b%2)!=0) { // 等同(a+b)%2 (因a為偶)
a= 3*a;
b= 3*b+1; // 3*(a+b)+1= (3*a) +(3*b+1)
}
a= a/2; // 每次疊代都會執行(a+b)/2
b= b/2;
}
}
設n為奇數且無--a,++b過程並假設每次的奇運搭配一個偶運算,則於測量點B可有:
a₁= n-1
aₓ= (3aₓ₋₁)/2 =... = (n-1)(3/2)ˣ⁻¹
b₁= 1
bₓ= (3bₓ₋₁+1)/2=... = 2(3/2)ˣ⁻¹ -1
aₓ/bₓ= (aₓ₋₁)/(bₓ₋₁) = ((n-1)(3/2)ˣ⁻¹)/(2(3/2)ˣ⁻¹ -1)
=... = (n-1)/(2- 1/(3/2)ˣ⁻¹)
小結: aₓ/bₓ < aₓ₋₁/bₓ₋₁, 及 lim{x->∞} aₓ/bₓ= (n-1)/2.
因"約一半的極限值(n-1)/2"是遞迴成立的. 但此為估算值. aₓ,bₓ實際上
是非連續函數,還會穿插a/2,b/2,--a,++b 運算使得aₓ更小,bₓ更大.
因此可推斷: 實際的aₓ/bₓ值遞減至終值0,且最終a=0.
cop疊代序列n₁,n₂,n₃,...,nₓ 可視為一個串級放大過程:
(n₂/n₁)(n₃/n₂)(n₄/n₃)...(nₓ/nₓ₋₁)= nₓ/n₁
奇運算的放大率= (3x+1)/x =3+1/x ≒ 3 (數x大時)
偶運算的放大率= x/(2x) =1/2
nₒᵤₜ/nᵢₙ ≒ 3ˣ/2ʸ ≒ 1.585*(x/y) // 約正比於奇偶運算次數比例
設x表奇運算次數,y表偶運算次數.
a由n算至0的x/y比值小於 1/n= 1.585*(x/y) <=> 1/(1.585n) = x/y
nₓ由n算至n-1的x/y比值 (n-1)/n = 1.585(x/y) <=> (n-1)/(1.585*n) = x/y
因此,n>2時,對於相同於a由n算至0的奇偶運算過程而言, nₓ由n算至n-1的運算存有
過量的偶運算 (決定性的細節繁雜冗長,不詳述).
由nₓ<n必出現,即可以數學歸納法証明命題"cop(n)疊代運算必終止"成立.
[1] 實數含無限大. 循環小數為無理數. 皮亞諾公理系統難証∞∉ℕ. [REG_04]
https://sourceforge.net/projects/cscall/files/MisFiles/RealNumber2-zh.txt/download
函數(函式)::= f:A->B, 函數f為由集合A到集合B的1-1或多-1的映射.
離散的映射集合也可定義一個函數,不必是性質描述. 函數基本上有先驗定義與由映
射定義兩種定義.
映射::= 設f(a)=b, 'a'稱為f的輸入,引數或參數, a,b的配對<a,b>稱為f的一條/個映射.
映射的配對可表達很多事情,如,刺激-反應,測試-結果,様本-label,輸入-輸出,若X則
Y...推理/聯想/記憶/連結/投射等的描述等. 幾乎任何記錄,基至自然語句都可成為
映射.
計算(computation)::= 由基本[部份]的決定性運算到整體表現的一個動態系統的運算過程.
(非平行)計算是由模型的輸入到輸出(解答)的一步步,決定性的運作過程(即,問題解的
計算過程中為'漸近完成'). 輸入與輸出是由固定有限的[部份]所構成. [部份]是可
客觀操作的東西,可指文字符號. 每一[部份]都有位置與值屬性.
[註] 計算與數學/邏輯的理論推理是相關的(証明/推理也可視為一種計算). 若[部份]
是離散的,差不多可認為[部份]可由'(數位)電路邏輯'描述/構成(但原則上,任何
物理系統都可以). 電路邏輯有時序概念,有輸入/輸出,有穩態/非穩態. 傳統邏輯
較不適用於有時序性的命題敍述.
[註] 此'計算'定義仍適用於(目前的)類神經網路,但'可能'較不直接適用於量子計算.
帶參數問題::= 問題敍述中帶有參數(或代詞)的問題,一般可以如'Q(x)'表示. x常是不限長
的資料如數字,陣列,字串,集合,...或某複雜物件.
(計算機)問題::= '問題'是種描述已知,以求未知(解)的敍述. '計算機問題'必須以計算機
能處理的文字敍述呈現. 簡要地說, 由於問題敍述最終須處理成(廣義上的)算法. 計算
機問題敍述可說是一種算法的描述,只是相同問題可有不同的算法描述,反之亦同.
許多問題敍述大致上是描述一解集合S,並找尋S中的元素,或退求 ∃x∈S (或∀x∈S),
P(x)成立(或不成立).
基本上,把事物描述中的某部份設為未知(或一般化),就變成了一個問題.
指令::= 一種對於計算機基本[部份]操作的命令敍述. 基本[部份]的對象是固定的,其操作
功能是決定性的, 如,基本的指令: 寫讀/比較分枝,.. 搬運/轉換等.
[註] 類神經元的作用等價於一個指令運算.
演算法::= 一串指令,描述某項作業的[部份]一步步依序完成的流程(或稱指令敍述,流程
敍述,程式,或簡稱算法). 特別是,流程敍述可含條件分枝,可條件執行或重複執行指令.
複雜度理論或'理論知識'等重用性較高的問題較關心帶參數問題,因此,'演算法'也常指
這類帶參數問題的算法. 由於這種問題敍述中含有不限定數量物件的代詞,相應地,因
演算法敍述的長度固定,這類(非常數複雜度)演算法必須使用迴圈重複執行指令,且須
使用'指標'或間接定址(或稱索引定址)類的指令,以達成以固定指令處理可變範圍
[部份]之能力.
[註] ANN是種算式的實作表達. 類神經元可視為一種可回饋修正參數的'指令',因此
ANN也是種演算法(等效).
[註] 由以上'計算','問題敍述'及'演算法'定義,差不多可証Turing-Church猜想: 對於
任何由[部份]至[整體]的決定性計算問題,圖靈機皆可表達.
離散連續性:: 若函數f可以單調區間分割,則f具有離散連續性.
演算法問題::= 計算步驟爲問題敍述長度(size)的函數的計算機問題. 此問題能以漸近
(asymptotic)方式描述問題size與計算步驟間的關係.
多項式時間程序(或稱Ptime程序)::= O(P)個連續,固定size的基本運算(因爲程序爲一
決定性過程,所以有時也稱"函式","函數"或"運算"). 因此,由O(P)定義,連續O(P)個
執行的Ptime程序整體也可視爲單一個Ptime程序.
歸約::= 計算問題A(的演算法)可以Ptime程序轉換成計算問題B,記爲A≤B (因Ptime轉換本身
即包含計算A問題,所以任ℙ問題間皆可相互歸約).
ANP::= {q| q爲計算機可以以下fnp算法模板在O(2^|q|)步驟內解決的判斷性問題敍述. q中
包含一驗証資料集合C, card(C)<=O(2^|q|),及Ptime驗証函式 v:C->{true,false}.
若∃c,v(c)=true, 則問題q的答案是true, 否則為false}
// begin_certificate 為一Ptime函數, 由問題敍述q中取出第一個Certificate元素.
// 若此元素不存在,則返回唯一且虚擬的虚擬的EndC元素.
Certificate begin_certificate(Problem q);
// end_certificate 為一Ptime函數, 由問題敍述q中取出元素EndC.
Certificate end_certificate(Problem q);
// next_certificate 為一Ptime函數, 由驗証資料集合C中取出c的下個元素. 若此元素
// 不存在,則返回EndC元素.
Certificate next_certificate(Problem q, Certificate c);
// v為一Ptime函數. v(c)==true iff c為問題所期待的元素.
bool v(Certificate c);
bool fnp(Problem q) {
Certificate c,begin,end; // 宣告驗證資料變數
begin= begin_certificate(q); // begin爲第一個驗證資料
end = end_certificate(q); // end爲用於表示結束的假資料EndC
for(c=begin; c!=end;
c=next_certificate(q,c)) { // 最多O(2^|q|)迴圈. next_certificate(c)
// 爲求取c的下個驗証資料的Ptime函式
if(v(c)==true) return true; // v:C->{true,false} 爲多項式時間的驗證函式.
}
return false;
}
由於連續O(P)數量的Ptime函數(或指令)可合併算成單一個Ptime函數,差不多於此複雜度
分析時,可在算法步驟中任增删,合併/分割任Ptime函數而不影響算法的複雜度. 或許最後
只需考慮判斷分枝的數量.
ANP問題q可以q<v,C>表達, v=Ptime驗証函式, C=驗証資料集合(敍述).
[註] [邱奇-圖靈猜想]也支持這種觀點: 没有形式語言的表達能力可超越圖靈機(或算法,
即由部份至整體的決定性運算過程)表達能力. C語言可視為圖靈機的高階語言,而
作為知識或証明的形式(formal)語言.
命題1: ANP=ℕℙ
証: ℕℙ ⊆ ANP 且 ANP ⊆ ℕℙ, 故ANP=ℕℙ.
(ANP與傳統圖靈機定義的ℕℙ等價証明細節平直冗長,對多數人而言不甚重要.
雖ANP定義不依賴NDTM理論, 但已有上千個實際的ℕℙℂ問題可供驗証參考)
命題2: ANP問題q<v,C>可任意分割成兩個子問題q1<v,C1>,q2<v,C2), C= C1∪C2.
証: 可將驗証資料集合二分割遞迴處理如下:
bool banp(Problem q) {
if(certificate_size(q)<Thresh) { // Thresh爲一值小的常數
return solve_thresh_case(q); // 常數時間內解算q
}
Problem q1,q2;
split_certificate(q,q1,q2); // 將q中的驗証資料集C二分組成size略
// 相同abs(|q1|-|q2|)<=1的q1及q2
return banp(q1) || banp(q2); // 分別計算子問題
}
命題3: 任兩ANP問題q1,q2可合成另一ANP問題q, 可記爲q=q1⊕ q2. q的驗証資料集合C及
驗証函式v分別如下定義:
C= C1 ∪ C2 // C1,C2分別爲q1,q2的驗証資料集合
bool v(x) {
return v1(x) || v2(x); // v1,v2分別爲q1,q2的驗証函式
}
因此,可有恆等式: q1<v1,C1>⊕ q2<v2,C2> = q<v1||v2, C1∪C2> (⊕ 的代數運算
規則同算術的加法).
命題4: ℕℙℂ問題q的驗証資料數量為O(2^|q|)等級
証: 若ℕℙℂ問題q的驗証資料數量不為O(2^|q|)等級,則ANP問題無法全歸約至q問題.
命題5: ℕℙℂ問題的複雜度為O(2^N)
証: 計算是個漸近過程. 計算機經過n步驟計算後的狀態總可分為成果與剩餘問題兩部份.
已知banp為O(2^N)的算法. 我們可於banp加入稱為'輔助資訊'的AuxInfo物件,存放
計算完某問題q後的成果, 而改寫成banp2. 視輔助資訊內容而定,banp2可表複雜度由
O(N)至O(2^N)的ANP/ℕℙℂ問題可能的算法. 以下分析主要針對ℕℙℂ問題.
bool banp2(Problem q, AuxInfo* ibuf) { // 計算q,並將所得輔助資訊寫至*ibuf
// 檢查及及初設 *ibuf
if(certificate_size(q)<Thresh) {
return solve_thresh_case(q,ibuf);
}
Problem q1,q2;
split_certificate(q,q1,q2);// 分割函式(任意Ptime算法)轉換q至子問題q1,q2.
AuxInfo I; // I存放輔助解題資訊.
if(banp2(q1,&I)==true) { // banp2(q1,I)遞迴計算子問題q1並將任何能由q1
// 導出的有用資訊並存於I. I只含有與問題q1的
// 驗証資料集C1相關的資訊才有義意,因若非相關,
// 其它子問題可以同様代價自行計算.
write_ibuf1(ibuf,q); // 寫出輔助資訊.
return true; // 由此子問題q1獲得的資訊對任問題q都有效(?).
}
bool rv=banp2_i(q2,&I); // 給予I資訊情況下解算q2, 任問題來源的資訊I皆
// 對q2有效(?).
write_ibuf2(ibuf,q);
return rv;
}
banp2能產生對其它所有問題都能提供足夠加速計算至改善複雜度級數程度的輔助
資訊I是不可能的,因I資訊的I/O會須要無限的空間/時間. 因此,ℕℙℂ問題的複雜度
不小於O(2^N).
結論: 由命題5,ℕℙℂ複雜度為O(2^N),故ℙ≠ℕℙ.
[1] THEORY OF COMPUTATION [Deric Wood]
[2] ALGORITHMICS, Theory and Practice [Gilles Brassard, Paul Bratley]
[3] AN INTRODUCTION TO FORMAL LANGUAGES AND AUTOMATA [Peter Linz]
[4] https://sourceforge.net/projects/cscall/files/MisFiles/Computation-zh.txt/download
(計算概念及術語定義)
[5] https://sourceforge.net/projects/cscall/files/MisFiles/C_as_TM-en.txt/download
(C語言圖靈機)
無限(非有限)(infinity)本質上是一個不終止的程序迴圈. 但在理解,應用上易有混淆(如有
所謂潛無限,實無限,..等).
作爲數學邏輯基礎的皮亞諾(Peano)公理有個嚴重缺陷: 沒有終止說明,不能完全証明"∞∉ℕ"
(若數的定義/推理都須依賴皮亞諾公理). 這導致許多有關無限大的理論,包含稠密性等定律
的應用及一些邏輯理論也跟著有相同的盲點與失誤.
此文所述與不少人的想法不同,所以嚴格論証是必要的(但不全然可行). 另方面,行文也須使
中(小)學生以上人士易於理解. 因此省略一些形式邏輯煩瑣,抽象的步驟,只點出重點(事實
上,"編理論"不是此文重點. 本質理解後,任人都能依應用編理論). 幸運的是, 將無限大
解釋為迴圈的實物概念易理解及應用(相對地,網路上不少簡單東西是能寫多抽象就寫多抽象
的問題理論,由其遇上實數). 但因應需要,後續有些新增重編,中小學生看不懂的可以跳過.
程序描述(或演算法)比一般建立傳統邏輯的形式系統更具表達能力(參考:邱奇-圖靈猜想
Church-Turing Thesis).
1.一般形式公理系統中的術語/符號常過當使用,難從所謂的"抽象數學概念"中客觀地
推斷出任何東西或根本就是抽象中的抽象,結果仍常是主觀想像,也常比簡單地使用
自然語言更糟糕.
2.一般(目前)形式系統無法描述程序性事實,而程序性邏輯已用於設計各種數位電腦並
驗証無誤.
因此,必要時,本文會使用虛擬C程式語言描述,但儘量可編譯.
typedef String NaturalNumber; // "符號為有限長的字串" 可算是公理中的公理
NaturnalNumber ℕ[]={0}; // 假設N陣列容量無上限(非實際所示)
NaturnalNumber next_natural_num(NaturnalNumber n) {
return mak_next(ℕ,m); // 由m,ℕ,製造下一個自然數
}
bool is_natural_num(n) {
if(is_format_correct(n)==false) { return false; }
if(contain(ℕ,n)) return true;
N m= get_max(ℕ);
for(;;) {
m=mak_next(ℕ,m);
insert(ℕ,m); // 將m加入ℕ陣列
if(n==m) return true;
}
return false; // unreachable
}
以上程式敍述可說明: 1.'數'基本上是符合符號格式及next_natural_num 或'後繼'
函數,..等操作的字串(如同操作以石子,棍子等構成的表達式). 2.'所有自然數'的義意
是指可任意指定(的自然數). '所有自然數的集合ℕ'不意味已實存無限多的自然數集ℕ.
註: 數學上的'自然數'是個沒有實質的抽象概念. 於推論中,若自然語言的抽象論証
涉及兩個自然數集時易出錯, 如若'另一自然數'集合N定義為'偶數'{0,2,4,6,.},
則N中的2,6不是N所定義的偶數,比較推論時,'偶數'的義意出現混淆. 若使用
程式表達或改善符號用法,如N<1,S>, N<0,+2>,...則錯誤較不易發生.
公理1: 自然數爲有限計數步驟的有限長度的離散符號.
公理2: 物件(如:數,形)與其(操作)性質同時由定義而存在.
公理3: 理論的語意最後必須對應物理現實 (否則無法客觀驗証/傳遞/應用).
符號'='::= a=b iff a-b=0
等號'='的義意有時很模糊. 此定義的目的僅於義意有疑問或未定義時,'參考使用'.
由公理2, 數(0)與其+/-運算須同時定義才能使用此定義判斷"相同".
命題1: ℕ+ℕ=ℕ (或設a,b∈ℕ(自然數), 則a+b∈ℕ) 的表述僅於有限加法步驟才成立.
証: 非0自然數纍加嚴格增加. 無限步驟纍加會得無限長的數. 由公理1,這種數不是
自然數.
命題2: ℚ+ℚ=ℚ (有理數與有理數的和仍爲有理數) 的表述僅於有限加法步驟才成立.
証: 正有理數q纍加嚴格增加,無限項q=a/b=q₁+q₂+q₃...時,a或b必然含無限大數 (或說,
結果不是'發散'就是'收斂'. 兩者皆含無限長的'自然數', 否則不能稱作是'收斂'
或發散).
以上命題引發一個問題:
a+b= (a+b) ... 得可疑結論 a,b∈N => a+b∈N (或應用次數的問題須解釋)
a/b+c/d= (ad+cb)/bd ... 得可疑結論 a,b∈ℚ => a+b∈ℚ (不恆成立)
所以,(目前的)形式邏輯無法處理這類含無限程序概念的命題.
命題3: 循環小數爲無理數.
証: 設循環小數x, 0<x<1, x有循環節S,並以進制法寫爲 x=0.S₁S₂S₃...S∞ 形式.
則依定義x= S₁/b +S₂/b² +S₃/b³ +... +S∞/b^∞ = q₁ +q₂ +q₃ +...+q∞ (b∈ℕ).
也就是說,循環小數為"ℚ+ℚ"的一個特例. 由命題2,無限加項時,x不是有理數(即無理
理).
註: 順便簡短說明常見的代數魔術:
(1) x= 0.999...
(2{ 10x= 9.999... // 可能隱含地定義了0.999...為1
(3) 10x= 9+x
(4) 9x=9
(5) x=1
解答: 沒有公理或定理可証 (1)<=>(3).
(3)是(1)的無限多種解釋中的一種解釋,或(3)爲0.999...的'引入'定義,..,等
總之,(3), (1)間無必然關係,或仍須証明. 譬如1/2+1/4+1/8+... 構成的
0.999...就没有(3)性質.
其它例子其實還很多, 譬如:
命題4: 程序敍述中含有不可判定(undecidable)的敍述.
証:
bool H(void(*)()); // 設H為一判別程序. H(D)==true iff D()正常結束運算.
// 若H存在,則有類似說謊者悖論的D,使得H(D)無法正確判定
void D() {
if(H(D)==true) for(;;){};
}
若將H視為一命題敍述,則此命題為不可判定(undecidable)命題.
註: 古典停機問題(Halting Problem)証法常用以上方式概要說明,但內容很不同,不涉及
無限自參.
註: 另種涉及無限自參的'誠實者悖論'命題也是不終結,如:
bool P() { // "我的這句話為真"
return P();
}
或模擬器/UTM 無法模擬自己.
命題5: 皮亞諾公理系統無法証明無限大是或不是自然數.
証: 後續產生器S不終結. 若'証明'的義意是完全如三段論式的產生形式,則皮亞諾公理
系統無法產生"∞∈ℕ","∞∉ℕ"這種鈙述.
命題6: 演算法(圖靈機模型)比皮亞諾公理系統更有表達力.
証: 我們可以比較兩個產生無限大的演算法是否相同,皮亞諾公理系統無法做到這點.
無限大的概念是由應用產生. 就程序觀點,'無限'的語意是指一永不終止的迴圈執行無限
多的運算步驟:
for(;;) {
P(); // 性質P或運算P
}
// unreachable
for迴圈中可有各種不同的命題P而解釋各種重複語意的概念,如無限級數的語意,
無限大/小,無限自參,不可判定,.. 都可以迴圈明確表述.
符號'∞'::= 表示某無限大的數,其'值'可說是永遠變動或不定數.
無限大可用一不終止的程序迴圈描述. 每個無限大數(若視為'數')可有以下代數運算
規則:
註: 只要遵守代數規則, '∞'的運算安全有效.
無限大數∞表示運算步驟不終止. 在運算表達式中,∞的義意必須固定唯一.
譬如: 若∞+1=∞ 成立, 則極限 lim(n->∞) 1/n 的'趨近'無義意. 因我們將不能分辨
n+1或n-1 那個是趨近那個是遠離. 若∞的義意固定,則我們可確定每朝無限遠
走一步,之間的距離就少一步 ("∞+1=∞ <=> 1=0"是個矛盾表達式. 若矛盾式能
由解釋或'証明'成立,則整個數學及此檔案就沒啥好談的. 某些邏輯理論也有
類似問題. 矛盾就是矛盾,編理論使矛盾成立或合理化是自找麻煩).
命題7: 無限大的數有無限多個.
証: 如∞+1,∞+2,2^∞,... 這種數有無限多個 (一般的'無限大'常是指一個集合).
命題8: 實數中包含無限大及無限小.
証: 實數的運算涉及無限操作步驟(如圓周長,正方形對角線長,極限,微積分,級數中的
無限項加總),故∞∈ℝ. 由於實數運算須封閉,故,實數也包含無限小(1/∞∈ℝ).
又如: x>0 <=> x/2 >0 恆成立. 因實數引入無限步驟.
故 x>0 <=> x/2>0 <=> x/4>0 <=> ... <=> x/2^∞ >0 <=> "無限小>0"
實數若不含無限大/小,則含無限大/小的敍述都不是嚴格合格有效的數學敍述(若換用
類如'無上界'等概念也不能解釋為何'無上界'個有理數的和會是無理數).
註: '抽象理論'於處理難解題時常用的手法是發明另種詞(概念)作為解釋,且可能很長.
較誇張比喻: 設某命題的証明有10^100頁(各種超級電腦無法處理). 若有人質疑其中
某部份或某名詞,其結果也是10^100頁解釋,這種理論無法
iThome鐵人賽
看影片追技術